#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int PathSum(TreeNode* root)
    {
        if (root == nullptr) return 0;

        int left = PathSum(root->left);
        int right = PathSum(root->right);
        int value = root->val;
        if (left > 0) root->val += left;
        if (right > 0) root->val += right;
        return max(value + left, value + right);
    }
    int maxSum(TreeNode* root)
    {
        if (root == nullptr) return -1000;
        int left = maxSum(root->left);
        int right = maxSum(root->right);

        return max(root->val, max(left, right));
    }
    int maxPathSum(TreeNode* root) {
        PathSum(root);
        return maxSum(root);
    }
};